%------------------------------------------------------------------------------
% Copyright (c) 1991-2014, Xavier Leroy and Didier Remy.
%
% All rights reserved. Distributed under a creative commons
% attribution-non-commercial-share alike 2.0 France license.
% http://creativecommons.org/licenses/by-nc-sa/2.0/fr/
%
% Translation by Mark Wong-VanHaren
%------------------------------------------------------------------------------

\chapter{\label{sec/processes}Processes}
\cutname{processes.html}

A process is a program executing on the operating system.  It
consists of a program (machine code) and a state of the program
(current control point, variable values, call stack, open file
descriptors, \etc).

This section presents the Unix system calls to create new processes
and make them run other programs.

\section{Creation of processes}

The system call \syscall{fork} creates a process.
%
\begin{listingcodefile}{tmpunix.mli}
val $\libvalue{Unix}{fork}$ : unit -> int
\end{listingcodefile}
%
The new \emph{child process} is a nearly perfect clone of the
\emph{parent process} which called \ml+fork+.  Both processes execute
the same code, are initially at the same control point (the return
from \ml+fork+), attribute the same values to all variables, have
identical call stacks, and hold open the same file descriptors to
the same files.  The only thing which distinguishes the two processes
is the return value from \ml+fork+: zero in the child process,
and a non-zero integer in the parent.  By checking the return value
from \ml+fork+, a program can thus determine if it is in the parent
process or the child and behave accordingly: 
%
\begin{lstlisting}
match fork () with
| 0 ->   (* code run only in the child  *)
| pid -> (* code run only in the parent *)
\end{lstlisting}
%
The non-zero integer returned by \ml+fork+ in the parent process
is the \emph{process id} of the child.  The process id is used by
the kernel to uniquely identify each process.  A process can obtain
its process id by calling \indexlibvalue{Unix}{getpid}.

The child process is initially in the same state as the parent process
(same variable values, same open file descriptors).  This state is not
shared between the parent and the child, but merely duplicated at the
moment of the \ml+fork+.  For example, if one variable is bound to a
reference before the \ml+fork+, a copy of that reference and its
current contents is made at the moment of the \ml+fork+; after the
\ml+fork+, each process independently modifies its \quotes{own}
reference without affecting the other process.

Similarly, the open file descriptors are copied at the moment of the
\ml+fork+: one may be closed and the other kept open.  On the other
hand, the two descriptors designate the same entry in the file table
(residing in system memory) and share their current position: if one
reads and then the other, each will read a different part of the file;
likewise, changes in the read/write position by one process with \ml+lseek+ are
immediately visible to the other. 

%% I don't think that's very enlighting at this point. 
% The descriptors in the child and
% parent thus act like the argument and result descriptors after a
% \ml+dup+, but they are in different processes as opposed to the same
% one.

\section{Complete Example: the command {\normalfont\texttt{leave}}}

The command \ml+leave hhmm+ exits immediately, but
forks a background process which, at the time \ml+hhmm+, reports that
it is time to leave.
%
\begin{listingcodefile}[style=numbers]{leave.ml}open Sys;;
open Unix;;

let leave () =
 let hh = int_of_string (String.sub Sys.argv.(1) 0 2)
 and mm = int_of_string (String.sub Sys.argv.(1) 2 2) in
 let now = localtime(time ()) in
 let delay = (hh - now.tm_hour) * 3600 + (mm - now.tm_min) * 60 in
$\label{prog:delay}$
 if delay <= 0 then begin
   print_endline "Hey! That time has already passed!";
   exit 0
 end;
 if fork () <> 0 then exit 0;
 sleep delay;
 print_endline "\007\007\007Time to leave!";
 exit 0;;

handle_unix_error leave ();;
\end{listingcodefile}
% 
The program begins with a rudimentary parsing of the command line,
in order to extract the time provided.  It then calculates the delay
in seconds (line~\ref{prog:delay}). The \indexlibvalue{Unix}{time}
call returns the current date, in seconds from the epoch (January 1st
1970, midnight).  The function \indexlibvalue{Unix}{localtime} splits
this duration into years, months, days, hours, minutes and seconds.
It then creates a new process using \ml+fork+.  The parent process
(whose return value from \ml+fork+ is a non-zero integer) terminates
immediately.  The shell which launched \ml+leave+ thereby returns
control to the user.  The child process (whose return value from
\ml+fork+ is zero) continues executing.  It does nothing during the
indicated time (the call to \ml+sleep+), then displays its message and
terminates.

\section{Awaiting the termination of a process}

The system call \ml+wait+ waits for one of the child processes created
by \ml+fork+ to terminate and returns information about how it did.
It provides a parent-child synchronization mechanism and a very
rudimentary form of communication from the child to the parent.
\label{wait}
%
\begin{codefile}{tmpunix.mli}
type process_status = Unix.process_status
type wait_flag = Unix.wait_flag
\end{codefile}
%
\begin{listingcodefile}{tmpunix.mli}
val $\indexlibvalue{Unix}{wait}$ : unit -> int * process_status
val $\libvalue{Unix}{waitpid}$ : wait_flag list -> int -> int * process_status
\end{listingcodefile}
%
The primitive system call is \syscall{waitpid} and the function
\ml+wait ()+ is merely a shortcut for the expression \ml+waitpid [] (-1)+.
% 
The behavior of \ml+waitpid [] p+ depends on the value of \ml+p+:
\begin{itemize}
\item If \ml+p+ $> 0$, it awaits the termination of the child with id
  equal to \ml+p+.
\item If \ml+p+ $= 0$, it awaits any child with the same group id as the
calling process. 
\item If \ml+p+ $= -1$, it awaits any process.
\item If \ml+p+ $<-1$, it awaits a child process with group id equal
  to \ml+-p+.
\end{itemize}
The first component of the result is the process id of the child
caught by \ml+wait+. The second component of the result is a value of type 
\libtype{Unix}{process\_status}:
%
\begin{mltypecases}
\begin{tabular}{@{}lp{0.8\textwidth}}
\ml+WEXITED r+ & The child process terminated normally via
\ml+exit+ or by reaching the end of the program; \ml+r+ is the return
code (the argument passed to \ml+exit+).\\
%
\ml+WSIGNALED s+ & The child process was killed by a signal
(ctrl-C, \ml+kill+, \etc, see chapter~\ref{sec/signals}
for more information about signals); \ml+s+ identifies the signal.\\
%
\ml+WSTOPPED s+ & The child process was halted by the signal
\ml+s+; this occurs only in very special cases where a process
(typically a debugger) is currently monitoring the execution of
another (by calling \ml+ptrace+).
\end{tabular}
\end{mltypecases}
%
If one of the child processes has already terminated by the time the
parent calls \ml+wait+, the call returns immediately.  Otherwise, the
parent process blocks until some child process terminates (a behavior
called \quotes{rendezvous}). To wait for $n$ child processes, one must
call \ml+wait+ $n$ times.

The command \ml+waitpid+ accepts two optional flags for its first
argument: the flag \ml+WNOHANG+ indicates not to wait if there is
a child that responds to the request but has not yet terminated.
In that case, the first result is \ml+0+ and the second undefined.
The flag \ml+WUNTRACED+ returns the child processes that have been
halted by the signal \ml+sigstop+.  The command raises the exception
\ml+ECHILD+ if no child processes match \ml+p+ (in particular, if
\ml+p+ is \ml+-1+ and the current process has no more children).

\begin{example}
\label{ex/forksearch}
The function \ml+fork_search+ below performs a linear search in an 
array with two processes. It relies on the function \ml+simple_search+
to perform the linear search.
%
\begin{listingcodefile}[style=numbers]{forksearch.ml}
open Unix;;
exception Found;;

let simple_search cond v =
 try
   for i = 0 to Array.length v - 1 do
     if cond v.(i) then raise Found
   done;
   false
 with Found -> true;;

let fork_search cond v =
 let n = Array.length v in
 match fork () with
 | 0 ->
     let found = simple_search cond (Array.sub v (n/2) (n-n/2)) in $\label{prog:found}$
     exit (if found then 0 else 1) $\label{prog:searchexit}$
 | _ ->
     let found = simple_search cond (Array.sub v 0 (n/2)) in
     match wait () with
     | (pid, WEXITED retcode) -> found || (retcode = 0) $\label{prog:wexit}$
     | (pid, _)               -> failwith "fork_search";;$\label{prog:wwexit}$
\end{listingcodefile}
%
After the \ml+fork+, the child process traverses the upper half of
the table, and exits with the return code $1$ if it found an element
satisfying the predicate \ml+cond+, or $0$ otherwise
(lines~\ref{prog:found} and~\ref{prog:searchexit}). The parent process
traverses the lower half of the table, then calls \ml+wait+ to
sync with the child process (lines~\ref{prog:wexit}
and~\ref{prog:wwexit}). If the child terminated normally, it combines
its return code with the boolean result of the search in the lower
half of the table. Otherwise, something horrible happened, and the
function \ml+fork_search+ fails.
\end{example}

In addition to the synchronization between processes, the \ml+wait+
call also ensures recovery of all resources used by the child
processes.  When a process terminates, it moves into a \quotes{zombie}
state, where most, but not all, of its resources (memory, \etc) have
been freed. It continues to occupy a slot in the process table to
transmit its return value to the parent via the \ml+wait+ call.
Once the parent calls \ml+wait+, the zombie process is removed from
the process table. Since this table is of fixed size, it is important
to call \ml+wait+ on each forked process to avoid leaks.

\label{double-fork}
If the parent process terminates before the child, the child is
given the process number~$1$ (usually \ml+init+) as parent. This
process contains an infinite loop of \ml+wait+ calls, and will
therefore make the child process disappear once it finishes. This
leads to the useful \quotes{double fork} technique if you cannot
easily call \ml+wait+ on each process you create (because you cannot
afford to block on termination of the child process,
for example).
%
\begin{lstlisting}
match fork () with
| 0 -> if fork () <> 0 then exit 0; 
      (* do whatever the child should do *)
| _ -> wait ();
      (* do whatever the parent should do *)
\end{lstlisting}
%
The child terminates via \ml+exit+ just after the second \ml+fork+.
The grandson becomes an orphan, and is adopted by \ml+init+.  In this
way, it leaves no zombie processes. The parent immediately calls
\ml+wait+ to reap the child. This \ml+wait+ will not block for long
since the child terminates very quickly.

\medskip

\section{Launching a program}

The system calls \syscall{execve}, \syscall{execv}, and
\syscall{execvp} launch a program within the current process.
Except in case of error, these calls never return: they halt the progress
of the current program and switch to the new program.
%
\begin{listingcodefile}{tmpunix.mli}
val $\libvalue{Unix}{execve}$ : string -> string array -> string array -> unit
val $\libvalue{Unix}{execv}$  : string -> string array -> unit
val $\libvalue{Unix}{execvp}$ : string -> string array -> unit
\end{listingcodefile}
%
The first argument is the name of the file containing the program to
execute. In the case of \ml+execvp+, this name is looked for in the
directories of the search path (specified in the environment variable
\ml+PATH+).

\pagebreak

The second argument is the array of command line arguments with which
to execute the program; this array will be the \ml+Sys.argv+ array 
of the executed program.

In the case of \ml+execve+, the third argument is the environment
given to the executed program; \ml+execv+ and \ml+execvp+
give the current environment unchanged.

The calls \ml+execve+, \ml+execv+, and \ml+execvp+ never return a
result: either everything works without errors and the process starts
the requested program or an error occurs (file not found, \etc), and
the call raises the exception \ml+Unix_error+ in the calling program.

\begin{example}
The following three forms are equivalent:
\begin{lstlisting}
execve "/bin/ls" [|"ls"; "-l"; "/tmp"|] (environment ())
execv  "/bin/ls" [|"ls"; "-l"; "/tmp"|]
execvp "ls"      [|"ls"; "-l"; "/tmp"|]
\end{lstlisting}
\end{example}

\begin{example}
Here is a \quotes{wrapper} around the command \ml+grep+ which
adds the option \ml+-i+ (to ignore case) to the list of arguments:
%
\begin{listingcodefile}{grep.ml}
open Sys;;
open Unix;;
let grep () =
 execvp "grep"
   (Array.concat
      [ [|"grep"; "-i"|];
        (Array.sub Sys.argv 1 (Array.length Sys.argv - 1)) ])
;;
handle_unix_error grep ();;
\end{listingcodefile}
\end{example}

\begin{example}
Here's a \quotes{wrapper} around the command \ml+emacs+ which
changes the terminal type:
%
\begin{listingcodefile}{emacs.ml}
open Sys;;
open Unix;;
let emacs () =
 execve "/usr/bin/emacs" Sys.argv
   (Array.concat [ [|"TERM=hacked-xterm"|]; (environment ()) ]);;
handle_unix_error emacs ();;
\end{listingcodefile}
\end{example}

The process which calls \ml+exec+ is the same one that executes the
new program.  As a result, the new program inherits some features of
the execution environment of the program which called \ml+exec+:
\begin{itemize}
\item the same process id and parent process
%% It's strange to say the following since the behavior is defined by
%% the parent, commented out.  
%, same behavior in relation to the parent process which called \ml+wait+
\item same standard input, standard output and standard error
\item same ignored signals (see chapter~\ref{sec/signals})
\end{itemize}

\section{Complete example: a mini-shell}

The following program is a simplified command interpreter: it reads
lines from standard input, breaks them into words, launches the
corresponding command, and repeats until the end of file on the
standard input.  We begin with the function which splits a string into
a list of words.  Please, no comments on this horror.

\begin{listingcodefile}{minishell.ml}
open Unix;;
open Printf;;

let split_words s =
 let rec skip_blanks i =
   if i < String.length s & s.[i] = ' '
   then skip_blanks (i+1)
   else i in
 let rec split start i =
   if i >= String.length s then
     [String.sub s start (i-start)]
   else if s.[i] = ' ' then
     let j = skip_blanks i in
     String.sub s start (i-start) :: split j j
   else
     split start (i+1) in
 Array.of_list (split 0 0);;
\end{listingcodefile}
%
We now move on to the main loop of the interpreter.
%
\begin{listingcodefile}{minishell.ml}
let exec_command cmd =
 try execvp cmd.(0) cmd
 with Unix_error(err, _, _) ->
   printf "Cannot execute %s : %s\n%!"
     cmd.(0) (error_message err);
   exit 255

let print_status program status =
 match status with
 | WEXITED 255 -> ()
 | WEXITED status ->
     printf "%s exited with code %d\n%!" program status;
 | WSIGNALED signal ->
     printf "%s killed by signal %d\n%!" program signal;
 | WSTOPPED signal ->
     printf "%s stopped (???)\n%!" program;;
\end{listingcodefile}
%
The function \ml+exec_command+ executes a command and handles errors.
The return code 255 indicates that the command could not be executed.
(This is not a standard convention; we just hope that few commands
terminate with a return code of 255.)  The function
\ml+print_status+ decodes and prints the status information returned
by a process, ignoring the return code of 255.
%
\begin{listingcodefile}{minishell.ml}
let minishell () =
 try
   while true do
     let cmd = input_line Pervasives.stdin in
     let words = split_words cmd in
     match fork () with
     | 0 -> exec_command words
     | pid_son ->
         let pid, status = wait () in
         print_status "Program" status
   done
 with End_of_file -> ()
;;

handle_unix_error minishell ();;
\end{listingcodefile}
% 
Each time through the loop, we read a line from \ml+stdin+ with the
function \ml+input_line+.  This function raises the \ml+End_of_file+
exception when the end of file is reached, causing the loop to
exit. We split the line into words, and then call \ml+fork+.  The
child process uses \ml+exec_command+ to execute the command.  The
parent process calls \ml+wait+ to wait for the command to finish and
prints the status information returned by \ml+wait+.

\begin{exercise}
\label{shell}
Add the ability to execute commands in the background if they are
followed by \ml+&+.
\end{exercise}
\begin{answer}
If the command line ends with \ml+&+, we do not call \ml+wait+ in
the parent process and immediately continue with the next iteration
of the loop. But there is one difficulty: the parent may now have
multiple children executing at the same time (the commands in the
background which haven't terminated yet, plus the last synchronous
command), and \ml+wait+ could synchronize with any of these children.
Thus, for synchronous command, \ml+wait+ must be repeated until the
recovered child is the one actually executing that command.
%
\begin{codefile}{shell.ml}
open Minishell
open Sys
open Unix
let parse_command_line cmd =
 let rec skip_blanks_backward i =
  if i >= 0 && cmd.[i] = ' ' then skip_blanks_backward (i-1) else i in
 let i = skip_blanks_backward (String.length cmd - 1) in
 let rest, ampersand =
  if i >= 0 && cmd.[i] = '&' then
    String.sub cmd 0 (1 + skip_blanks_backward (i-1)), true
  else cmd, false in
 split_words rest, ampersand
;;
let shell () =
 try
\end{codefile}
\begin{listingcodefile}{shell.ml}
   while true do
     let cmd = input_line Pervasives.stdin in
     let words, ampersand = parse_command_line cmd in
     match fork () with
     | 0 -> exec_command words
     | pid_son ->
         if ampersand then ()
         else
           let rec wait_for_son () =
             let pid, status = wait () in
             if pid = pid_son then
               print_status "Program" status
             else
               let p = "Background program " ^ (string_of_int pid) in
               print_status p status;
               wait_for_son () in
           wait_for_son ()
   done
\end{listingcodefile}
\begin{codefile}{shell.ml}
 with End_of_file -> ()
;;
handle_unix_error shell ();;
\end{codefile}
\end{answer}
